﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using SimpleIR;
using System.Diagnostics.Contracts;

namespace RgnAnalyzer.Domain
{
	/// <summary>
	/// This class represents reference typed values.
	/// </summary>
	internal struct AReference
	{
		/// <summary>
		/// The type of the reference
		/// </summary>
		private readonly IRReferenceType m_reftype;

		/// <summary>
		/// An array of all the possible targets for this reference.
		/// </summary>
		private readonly APossibleReferenceTarget[] m_reftrgts;

		/// <summary>
		/// A flag that represents if the reference may be null.
		/// </summary>
		private readonly bool m_maynull;

		/// <summary>
		/// To reduce GC pressure all null references share the same empty target set.
		/// </summary>
		private static readonly APossibleReferenceTarget[] EmptyRefTargets = new APossibleReferenceTarget[0];
		
		private AReference(IRReferenceType reftype, APossibleReferenceTarget[] rra, bool maynull)
		{
			Contract.Requires(reftype != null);
			Contract.Requires(rra != null);
			Contract.Requires((rra.Length != 0) | (rra == EmptyRefTargets), "Hmm, something went wrong.");
			Contract.Requires((rra.Length != 0) | (maynull), "Shouldn't be non-null with no targets.");

			this.m_reftype = reftype;
			this.m_reftrgts = rra;
			this.m_maynull = maynull;
		}

		internal AReference(IRReferenceType reftype, APossibleReferenceTarget r)
		{
			Contract.Requires(reftype != null);
			
			this.m_reftype = reftype;
			this.m_reftrgts = new APossibleReferenceTarget[] { r };
			this.m_maynull = false;
		}

		internal AReference CopyWithLimitedTargetSet(ATrgtEnum oktrgt)
		{
			if(this.m_reftrgts == EmptyRefTargets)
				return this;

			APossibleReferenceTarget aprt = this.m_reftrgts[oktrgt.PosKey];
			return new AReference(this.m_reftype, new APossibleReferenceTarget[] { aprt }, this.m_maynull);
		}

		internal static AReference CreateDefaultNullReference(IRReferenceType reftype)
		{
			Contract.Requires(reftype != null);

			return new AReference(reftype, EmptyRefTargets, true);
		}

		public override string ToString()
		{
			if(this.m_reftrgts == EmptyRefTargets)
				return "null";
			else
			{
				StringBuilder sb = new StringBuilder("[");
				for(int i = 0; i < this.m_reftrgts.Length; ++i)
				{
					if(i != 0)
						sb.Append(", ");
					sb.Append(this.m_reftrgts[i].ToString());
				}
				sb.Append("]");

				if(this.m_maynull)
					sb.Append("MayNull");

				return sb.ToString();
			}
		}

		/// <summary>
		/// Return true if the two arrays of pointer targets are the same (in the abstract sense).
		/// BUT WE ASSUME TARGET CONSISTENCY IS DONE IN THE EXTERNAL ISOMORPHISM CODE.
		/// </summary>
		internal static bool DomainEqualIgnoreTargets(AReference r1, AReference r2)
		{
			return (r1.m_reftrgts.Length == r2.m_reftrgts.Length) & (r1.m_maynull == r2.m_maynull);
		}

		/// <summary>
		/// Take two possible reference targets at the same abstract address and merge their info.
		/// </summary>
		internal AReference MergeOtherReferenceTargetWith(AReference ort)
		{
			Contract.Requires(this.ReferenceType == this.ReferenceType);

			if(this.m_reftrgts == EmptyRefTargets)
				return ort;
			else if(ort.m_reftrgts == EmptyRefTargets)
				return this;
			else
			{
				List<APossibleReferenceTarget> allrtt = new List<APossibleReferenceTarget>(this.m_reftrgts);
				
				int osize = allrtt.Count;
				for(int i = 0; i < ort.m_reftrgts.Length; ++i)
				{
					int posm = allrtt.BinarySearch(0, osize, ort.m_reftrgts[i], null);
					if(posm < 0)
						allrtt.Add(ort.m_reftrgts[i]);
				}

				return new AReference(this.m_reftype, allrtt.ToArray(), this.m_maynull | ort.m_maynull);
			}
		}

		/// <summary>
		/// Return the result of testing the two references for equality as a <c>ZeroOne.Value</c>
		/// </summary>
		internal static ZeroOne.Value ReferenceEqualsTest(AReference r1, AReference r2)
		{
			Contract.Requires(r1.ReferenceType == r2.ReferenceType);

			if(r1.m_reftrgts == EmptyRefTargets & r2.m_reftrgts == EmptyRefTargets)
				return ZeroOne.Value.One;
			else if(r1.m_reftrgts == EmptyRefTargets)
				return r2.m_maynull ? ZeroOne.Value.Unknown : ZeroOne.Value.Zero;
			else if(r2.m_reftrgts == EmptyRefTargets)
				return r1.m_maynull ? ZeroOne.Value.Unknown : ZeroOne.Value.Zero;
			else
				return ZeroOne.Value.Unknown;
		}

		/// <summary>
		/// Return the <c>ZeroOne.Value</c> encoding of the result of testing the reference for nullity
		/// </summary>
		internal ZeroOne.Value ReferenceNullTest()
		{
			if(this.m_reftrgts == EmptyRefTargets)
				return ZeroOne.Value.One;
			else if(this.m_maynull)
				return ZeroOne.Value.Unknown;
			else
				return ZeroOne.Value.Zero; 
		}

		internal IRReferenceType ReferenceType
		{ get { return this.m_reftype; } }

		/// <summary>
		/// Return the result of indexing the reference by the given field offset.
		/// </summary>
		internal AReference IndexAddrByFieldOrIndex(IRMemberField mf)
		{
			Contract.Requires(mf != null);

			APossibleReferenceTarget[] nrra = new APossibleReferenceTarget[this.m_reftrgts.Length];
			for(int i = 0; i < this.m_reftrgts.Length; ++i)
				nrra[i] = this.m_reftrgts[i].IndexAddrByField(mf);

			IRReferenceType rtt = GlobalAnalysisState.TProg.TypeTable.LookupReferenceTypeFor(mf.FieldType);
			return new AReference(rtt, nrra, this.m_maynull);
		}

		/// <summary>
		/// Convert the possible pointer targets into the equivalent reference
		/// </summary>
		internal static AReference ConvertToReference(IRReferenceType rtype, APossiblePointerTarget[] ppt, bool isnonnull)
		{
			if(ppt.Length == 0)
				return new AReference(rtype, EmptyRefTargets, false);
			else
			{
				APossibleReferenceTarget[] aprt = new APossibleReferenceTarget[ppt.Length];
				for(int i = 0; i < ppt.Length; ++i)
					aprt[i] = new APossibleReferenceTarget(ppt[i].PTarget, IRBasicAccessPath.EmptyAccessPath);

				return new AReference(rtype, aprt, !isnonnull);
			}
		}

		internal AReference AssertTargetNonNull()
		{
			Contract.Requires(this.RTargetCount != 0, "It must be null so this assertion is strange.");

			return new AReference(this.m_reftype, this.m_reftrgts, true);
		}

		/// <summary>
		/// Return true if this reference must be non-null.
		/// </summary>
		internal bool MustBeNonNull
		{ get { return !this.m_maynull; } }

		/// <summary>
		/// Return the number of possible reference targets for this (APossibleReferenceTarget).
		/// </summary>
		internal int RTargetCount
		{ get { return this.m_reftrgts.Length; } }

		/// <summary>
		/// Return the <c>index</c>th reference target (APossibleReferenceTarget).
		/// </summary>
		internal APossibleReferenceTarget GetIthPossibleRefTrgt(int index)
		{ return this.m_reftrgts[index]; }

		internal APossibleReferenceTarget ResolveRefFromEnum(ATrgtEnum tenum)
		{ return this.m_reftrgts[tenum.PosKey]; }

		internal IEnumerator<ATrgtEnum> GetATrgtEnumerator()
		{ return new RTEnumerator(this); }

		/// <summary>
		/// The enumerator we have to produce the targets in this.
		/// </summary>
		internal sealed class RTEnumerator : IEnumerator<ATrgtEnum>
		{
			private readonly AReference m_ref;
			private int m_rpos;

			internal RTEnumerator(AReference tref)
			{
				this.m_ref = tref;
				this.m_rpos = -1;
			}

			public ATrgtEnum Current
			{ get { return new ATrgtEnum(this.m_rpos, this.m_ref.GetIthPossibleRefTrgt(this.m_rpos)); } }

			public void Dispose()
			{ ;}

			object System.Collections.IEnumerator.Current
			{ get { return new ATrgtEnum(this.m_rpos, this.m_ref.GetIthPossibleRefTrgt(this.m_rpos)); } }

			public bool MoveNext()
			{
				if(this.m_rpos == this.m_ref.RTargetCount)
					return false;

				++this.m_rpos;
				return this.m_rpos < this.m_ref.RTargetCount;
			}

			public void Reset()
			{ this.m_rpos = -1; }
		}

		internal AReference DeletePossibleTargets(HashSet<int> deleteset)
		{
			if(this.m_reftrgts == EmptyRefTargets)
				return this;
			else
			{
				List<APossibleReferenceTarget> aprtl = new List<APossibleReferenceTarget>();

				for(int i = 0; i < this.m_reftrgts.Length; ++i)
				{
					if(!deleteset.Contains(this.m_reftrgts[i].RTarget))
						aprtl.Add(this.m_reftrgts[i]);
				}

				APossibleReferenceTarget[] rrt = (aprtl.Count == 0 ? EmptyRefTargets : aprtl.ToArray());
				bool nullity = (aprtl.Count == 0 ? true : this.m_maynull);

				return new AReference(this.m_reftype, rrt, nullity);
			}
		}

		/// <summary>
		/// During compaction after removing unreachable locations we update the addresses in the reference.
		/// </summary>
		internal AReference UpdateAddresses_ISOMapping(Dictionary<int, int> addrReMap)
		{
			Contract.Requires(addrReMap != null);

			if(this.m_reftrgts == EmptyRefTargets)
				return this;
			else
			{
				APossibleReferenceTarget[] upr = new APossibleReferenceTarget[this.m_reftrgts.Length];
				for(int i = 0; i < this.m_reftrgts.Length; ++i)
					upr[i] = this.m_reftrgts[i].UpdateTargetValue(addrReMap[this.m_reftrgts[i].RTarget]);

				Array.Sort(upr);
				return new AReference(this.m_reftype, upr, this.m_maynull);
			}
		}

		/// <summary>
		/// On normal form computation we merge equivalence classes from locations on the same flow history use this to replace old address sets with new sets.
		/// </summary>
		internal AReference UpdatedAddresses_MayMerge(Dictionary<int, int> addrReMap)
		{
			Contract.Requires(addrReMap != null);

			if(this.m_reftrgts == EmptyRefTargets)
				return this;
			else
			{
				HashSet<APossibleReferenceTarget> allrtt = new HashSet<APossibleReferenceTarget>();
				for(int i = 0; i < this.m_reftrgts.Length; ++i)
					allrtt.Add(this.m_reftrgts[i].UpdateTargetValue(addrReMap[this.m_reftrgts[i].RTarget]));

				APossibleReferenceTarget[] prra = new APossibleReferenceTarget[allrtt.Count];
				allrtt.CopyTo(prra);
				Array.Sort(prra);

				return new AReference(this.m_reftype, prra, this.m_maynull);
			}
		}

		internal AReference ReplaceAssociatedCutpointsAsNeeded(Dictionary<int, int> addressToCPIDMap)
		{
			if(this.m_reftrgts == EmptyRefTargets)
				return this;
			else
			{
				bool repl = false;
				for(int i = 0; i < this.m_reftrgts.Length; ++i)
					repl |= addressToCPIDMap.ContainsKey(this.m_reftrgts[i].RTarget);

				APossibleReferenceTarget[] nrra;
				if(!repl)
					nrra = this.m_reftrgts;
				else
				{
					nrra = new APossibleReferenceTarget[this.m_reftrgts.Length];
					for(int i = 0; i < this.m_reftrgts.Length; ++i)
					{
						int mrv = this.m_reftrgts[i].RTarget;
						if(addressToCPIDMap.ContainsKey(mrv))
							nrra[i] = this.m_reftrgts[i].UpdateTargetValue(addressToCPIDMap[mrv]);
						else
							nrra[i] = this.m_reftrgts[i];
					}
					Array.Sort(nrra);
				}

				return new AReference(this.m_reftype, nrra, this.m_maynull);
			}
		}

		internal AReference UpdateOutEdgesAfterCutpointEdgeExpand(Dictionary<int, int[]> cpidToAddressMap)
		{
			if(this.m_reftrgts == EmptyRefTargets)
				return this;
			else
			{
				bool hasexpand = false;
				for(int i = 0; i < this.m_reftrgts.Length; ++i)
					hasexpand |= cpidToAddressMap.ContainsKey(this.m_reftrgts[i].RTarget);

				APossibleReferenceTarget[] nrra;
				if(!hasexpand)
					nrra = this.m_reftrgts;
				else
				{
					HashSet<APossibleReferenceTarget> allrtt = new HashSet<APossibleReferenceTarget>();
					for(int i = 0; i < this.m_reftrgts.Length; ++i)
					{
						APossibleReferenceTarget aprt = this.m_reftrgts[i];
						if(!cpidToAddressMap.ContainsKey(aprt.RTarget))
							allrtt.Add(aprt);
						else
						{
							for(int j = 0; j < cpidToAddressMap[aprt.RTarget].Length; ++j)
								allrtt.Add(aprt.UpdateTargetValue(cpidToAddressMap[aprt.RTarget][j]));
						}
					}

					nrra = new APossibleReferenceTarget[allrtt.Count];
					allrtt.CopyTo(nrra);
					Array.Sort(nrra);
				}

				return new AReference(this.m_reftype, nrra, this.m_maynull);
			}
		}
	}

	/// <summary>
	/// Represents a possible reference target.
	/// </summary>
	internal struct APossibleReferenceTarget : IEquatable<APossibleReferenceTarget>, IComparable<APossibleReferenceTarget>
	{
		/// <summary>
		/// The target address
		/// </summary>
		internal readonly int RTarget;

		/// <summary>
		/// The target offset of the reference (where it refers to).
		/// </summary>
		internal readonly IRBasicAccessPath  TrgtOffset;

		internal APossibleReferenceTarget(int trgt, IRBasicAccessPath offset)
		{
			Contract.Requires(offset != null);
			
			this.RTarget = trgt;
			this.TrgtOffset = offset;
		}

		internal APossibleReferenceTarget UpdateTargetValue(int trgt)
		{ return new APossibleReferenceTarget(trgt, this.TrgtOffset); }

		/// <summary>
		/// Return the result of indexing the reference by the given field offset.
		/// </summary>
		internal APossibleReferenceTarget IndexAddrByField(IRMemberField mf)
		{
			//we are indexing again in the same array which is cool and we don't need to extend the path so just return.
			if(mf.IsSummaryField && this.TrgtOffset.Path.Length == 1 && this.TrgtOffset.PathFirst == mf)
				return this;

			IRBasicAccessPath extp = GlobalAnalysisState.TProg.GetAccessPathExtensionPost(this.TrgtOffset, mf);
			return new APossibleReferenceTarget(this.RTarget, extp);
		}

		/// <summary>
		/// Return true if the two edges are equal in the abstract doamin lattice sense.
		/// BUT WE ASSUME TARGET CONSISTENCY IS DONE IN THE EXTERNAL ISOMORPHISM CODE
		/// </summary>
		internal bool DomainEqualIgnoreTargetAddress(APossibleReferenceTarget opt)
		{
			return (this.TrgtOffset == opt.TrgtOffset);
		}

		public override string ToString()
		{ return this.RTarget + "." + this.TrgtOffset.ToString(); }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public static bool operator ==(APossibleReferenceTarget opt1, APossibleReferenceTarget opt2)
		{ return opt1.Equals(opt2); }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public static bool operator !=(APossibleReferenceTarget opt1, APossibleReferenceTarget opt2)
		{ return !opt1.Equals(opt2); }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public static bool operator <(APossibleReferenceTarget opt1, APossibleReferenceTarget opt2)
		{ return opt1.CompareTo(opt2) < 0; }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public static bool operator >(APossibleReferenceTarget opt1, APossibleReferenceTarget opt2)
		{ return opt1.CompareTo(opt2) > 0; }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public override int GetHashCode()
		{ return this.RTarget ^ this.TrgtOffset.GetHashCode(); }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public override bool Equals(Object obj)
		{ return (obj is APossibleReferenceTarget) && this.Equals((APossibleReferenceTarget)obj); }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public bool Equals(APossibleReferenceTarget other)
		{ return (this.RTarget == other.RTarget) & (this.TrgtOffset == other.TrgtOffset); }

		/// <summary>
		/// ONLY ON TARGET and PATH!!
		/// </summary>
		public int CompareTo(APossibleReferenceTarget other)
		{ return (this.RTarget != other.RTarget) ? (this.RTarget - other.RTarget) : this.TrgtOffset.CompareTo(other.TrgtOffset); }
	}
}
